A general framework for the rate-distortion optimized MB mode decision is provided by the minimization of the Lagrangian cost functionJ(m, λ)=D(m)+λ*R(m),  EQ 1where D measures the coding distortion, R represents the encoding bit cost, λ is Lagrangian multiplier, and m is one of macro-block coding modes/types supported in a video coding system. The mode leading to the lowest Lagrangian cost function among all macro-block coding modes is selected for encoding the current macro-block.
The calculation of actual coding distortion and bitrate for each candidate mode involves relatively high computational complexity. Therefore, the Lagrangian cost function is often approximated by the sum of absolute difference (SAD), given by
      SAD          X      ×      Y        =            ∑              X        ×        Y                                  ⁢                                  I          ⁡                      (                          x              ,              y                        )                          -                  I          *                      (                          x              ,              y                        )                                    where X and Y are the block width and height for SAD calculation, and I (x, y) and I* (x, y) represent the pixel value of the source input image at location (x, y) and its corresponding predicted pixel value from the recovered image regions, respectively.
For example, for the MPEG-4 AVC/H.264 video coding, one of the macro-block mode decision algorithm in the JVT reference software implementation approximates the Lagrangian R-D cost for I16×16 MB type, JI16×16, by
                                                                        J                                  116                  ×                  16                                            ⁡                              (                λ                )                                      ≡                          J              ⁡                              (                                                      116                    ×                    16                                    ,                  λ                                )                                              =                                    min                              0                <                m                <                4                                      ⁢                          SAD                              16                ×                16                            m                                      ,                            EQ        ⁢                                  ⁢        2            and the Lagrangian R-D cost for the I4×4 MB type, JI4×4, by
                                                                        J                                  14                  ×                  4                                            ⁡                              (                λ                )                                      ≡                          J              ⁡                              (                                                      14                    ×                    4                                    ,                  λ                                )                                              =                                    24              *              λ                        +                                          ∑                                  i                  ,                  j                                                                                              ⁢                              (                                                                            min                                              0                        ≤                        m                        <                        9                                                              ⁢                                                                  SAD                                                  4                          ×                          4                                                m                                            ⁡                                              (                                                  i                          ,                          j                                                )                                                                              +                                      QP                    ⁡                                          (                      λ                      )                                                                      )                                                    ,                            EQ        ⁢                                  ⁢        3            where (i, j) indicates the index for the current 4×4 block within the macro-block and QP(λ) accounts for the bit cost for encoding prediction mode information and is equal to 0 for the predicted mode and 4*λ otherwise.
The optimal macro-block mode decision among all candidate modes typically proceeds in an exhaustive approach, where rate-distortion costs are independently and fully calculated for individual candidate modes and the decision logic then selects the mode with a minimum R-D cost. An example related to macro-block mode decision in the MPEG-4 AVC/H.264 coding system is depicted in FIG. 4, where the optimal macro-block mode is selected among MPEG-4 AVC/H.264 macro-blocks types Inter, I16×16 and I4×4. The exhaustive approach then need to estimates the rate-distortion cost for each of three macro-block modes. Specifically, the calculation of the I4×4 R-D cost based on EQ 3 requires the reconstructed pixels from the top and left neighboring 4×4 blocks for predicting each 4×4 block inside the current macro-blocks. The cascaded encoding and decoding operation with high computational complexity therefore need to be performed on the individual 4×4 block in the macro-block to generate the recovered pixels for signal prediction. The resulting computational complexity is thus quite significant and often accounts for a large portion of the computational load of the overall encoding system.
Performing such an exhaustive search demands a vast amount of computational resource and is inefficient for practical video coding applications. Accordingly, embodiments of the invention are directed to a method that reduces the complexity associated with the search for the lowest cost function, J, by effectively exploiting the accumulated coding statistics collected across different prediction modes. Specific embodiments of the invention are developed for fast estimation of the rate-distortion cost associated with the intra macro-block mode for speed up of the encoder macro-block mode decision operation.